package com.example.learn

/**
 * 针对 [-4，2，10，9， 8， 7， 6]， 选中第3小的那个数， 并输出。
 */
fun main() {
    val arr = intArrayOf(-4, 2, 10, 9, 8, 7, 6)
    quickSort(arr, 0, arr.size - 1)
    arr.forEach {
        print("->$it")
    }
    println()
    println(arr[2])
}

fun quickSort(arr: IntArray, start: Int, end: Int) {
    if (start >= end || start < 0 || end < 0) return
    val q = partition(arr, start, end)
    quickSort(arr, start, q - 1)
    quickSort(arr, q + 1, end)
}

private fun partition(arr: IntArray, start: Int, end: Int): Int {
    val pivot = arr[end]
    var i = start
    for (j in start .. end) {
        if (arr[j] < pivot) {
            val tmp = arr[i]
            arr[i] = arr[j]
            arr[j] = tmp
            i ++
        }
    }
    val tmp = arr[i]
    arr[i] = arr[end]
    arr[end] = tmp
    return i
}